Advancements in digital technology have produced a number of digital video applications. Digital video is currently used in digital and high definition television (HDTV), video conferencing, computer imaging, and high quality video tape recorders. Uncompressed digital video signals constitute a huge amount of data and therefore require a large amount of bandwidth and memory to store and transmit. For example, one of the formats defined for HDTV broadcasting within the United States is 1920 pixels horizontally by 1080 lines vertically, at 30 frames per second. If these numbers are all multiplied together, along with eight bits for each of the three primary colors, the total data rate required will be approximately 1.5 Gb/sec. Because of the 6 MHz channel bandwidth limitation imposed by the FCC, each channel only supports a date rate of 19.2 Mb/sec, which is further reduced to 18 Mb/sec because the channel must also support audio, transport, and ancillary data information. Given the transmission data rate restriction, the original signal must be compressed by a factor of approximately 83:1. Many digital video systems, therefore, reduce the amount of digital video data by employing data compression techniques that are optimized for particular applications. Digital compression devices are commonly referred to “encoders”, while devices that perform decompression are referred to as “decoders”. Devices that perform both encoding and decoding are often referred to as “codecs”.
In the interests of standardizing methods for motion picture video compression, the moving picture experts group (MPEG) issued a number of standards for digital video processing.
Motion picture video sequences consist of a series of still pictures or “frames” that are sequentially displayed to provide the illusion of continuous motion. Each frame may be described as a two-dimensional array of picture elements or “pixels”. Each pixel describes a particular point in the picture in terms of brightness and hue. Methods have been devised to reduce the amount of transmission data required to represent each frame. The reduction of transmission data is referred to as data compression. Rather than transmitting large amounts of information for each pixel location's color and brightness, compression methods divide each frame into a predetermined number of “macroblocks”. The macroblocks are typically defined as a 16×16 array of pixels. Since there is some similarity within and between successive frames, it is more efficient to transmit only the differences between the frames if the current macroblock is found in a successive or preceding frame, it is more efficient to transmit a motion vector that details where to move the current macroblock. The motion vectors are determined by comparing each pixel location in the current macroblock with each pixel location in a successive reference frame. The integer location which differs the least between the two macroblocks is used to generate the motion vector. The process of searching every pixel location is referred to as a full or exhaustive search and the process of searching less than every pixel location is referred to as a fast search. A fast search algorithm for integer pixel locations is described in U.S. Pat. No. 6,128,047 entitled “Motion Estimation Process And System Using Sparse Search Block-Matching And Integral Projection”, to Chang et al.
The current macro block does not always shift an integer number of pixels in a given direction in real world video encoding. In reality, the macro block may be displaced by a fractional portion of a pixel. Several methods exist which obtain the integer pixel location previously determined by a Full or Fast search integer pixel search algorithm and perform a second search on all 8 surrounding half-pixel locations to more accurately define the motion vector. While this yields a more accurate motion vector, there is an increase in the number of computations necessary to locate the correct half-pixel location. There exist ½ pixel search algorithms that perform a fast search. i.e., not all 8½ pixel locations are searched. One such fast search algorithm is described in “Fast Two-Step Half-Pixel Accuracy Motion Vector Prediction”, K. H. Lee, J. H. Chol, B. K. Lee and D. G. Kim, Electronics Letters, 30 Mar. 2000 Vol. 36, no. 7. The Lee article performs a fast two-step half-pixel accuracy motion vector prediction algorithm by first determining which integer location of a macro block contains the lowest Mean of Absolute Difference (MAD). The MAD function is shown in equation (1):
                              MAD          ⁡                      (                          dx              ,              dy                        )                          =                              1            256                    ⁢                                    ∑                              i                =                0                            15                        ⁢                                                  ⁢                                          ∑                                  j                  =                  o                                15                            ⁢                                                                                    f                    ⁡                                          (                                              i                        ,                        j                                            )                                                        -                                      g                    ⁡                                          (                                                                        i                          -                                                      d                            ⁢                                                                                                                  ⁢                            x                                                                          ,                                                  j                          -                                                      d                            ⁢                                                                                                                  ⁢                            y                                                                                              )                                                                                                                                              (        1        )            where, f(i, j) represents a block of 16×16 pixels (macroblock) from the current frame, g(i, j) represents the same macroblock but from a reference frame (either previous or future in time), and the reference macroblock is displaced by a vector (dx, dy), representing the search location. The MAD function calculates which integer pixel location in a succeeding frame contains a minimum difference. This pixel value becomes the integer pixel displacement value for a motion vector.
To find the best matching block producing the minimum MAD value, we need to calculate the MAD at several locations in the search range. As mentioned previously, a full or exhaustive search calculates the MAD at all of the locations, while a fast or partial search selects predetermined values.
Referring to FIG. 1, the Lee article describes how the ½ pixel points surrounding the previously determined integer pixel location are tested. First, the surrounding half-pixel integer locations are separated into a horizontal and vertical pair Horizontal half-pixel points 2 and 7 and vertical half-pixel points 4 and 5 are interpolated based upon the surrounding integer pixel values and the MADs of location 2 as compared with location 7, and location 4 as compared with location 5 to determine a minimum MAD pair. The interpolated pixels are determined using MPEG approved bi-linear interpolation techniques. The block with the lowest MAD value is then compared with the blocks of the opposing pairs to determine a minimum pair. For example, assume that point 2 has the minimum MAD and 5 has a smaller MAD than 4, the minimum MAD pair is to be 2 and 5 and point 4 is additionally considered for half-pixel motion prediction. Finally, the half-pixel accuracy motion vector is determined by comparing the MADs of the centered integer pixel block, the minimum candidate block, and the most recently considered point.
While the Lee article describes a fast two step half-pixel motion vector prediction algorithm, the algorithm performs 5 calculations and only reduces the computational burden by 37.5% compared with that of the conventional full half-pixel search method. Accordingly, there remains a need for a fast half-pixel motion estimation algorithm which further reduces the computational burden of determining a half-pixel accuracy motion vector.